In computer graphics systems, it is desired to represent a two and three dimensional graphical picture on a two dimensional display. Typically, such a picture is a construct or image that may be stored in memory as a set of polygons or objects that are tessellated into polygons. To generate the picture on the display, the polygons are then rendered using processes that are typically computationally intensive.
FIG. 1 is an illustration of several graphical polygons to be rendered on a display 10. Polygon 20 is a quadrilateral defined by vertices A, B, C and D. Polygon 21 is a quadrilateral that has been overlapped by polygon 20. As a result, quadrilateral 21 has been modified to be a polygon with seven edges defined by vertices E, F, C, G, H, I and J. Polygon 22 is a triangle also overlapped by quadrilateral 20 such that triangle 22 is a six sided polygon defined by vertices K, L, M, N, B and O. Also shown is a circle that has been tessellated into eight triangles in order to efficiently render the circle using polygons with straight edges. The triangles comprising circle 25 are defined by vertices P, Q, R, S, T, U, V, W and X. For example, triangle 25A of tesselated circle 25 is defined by vertices P, T and U and triangle 25B is defined by vertices P, U and V.
Liang et al., U.S. Pat. No. 4,758,965, discloses one approach to filling polygons being displayed. Liang et al. teaches using two modified Bresenham line generators. The Bresenham line generators are used to generate the edges to the polygon for display while also providing parameters that can be used to generate fill lines connecting the edges by a separate hardware element.
One difficulty in rendering multiple polygons that overlap or touch, including Liang et al., is in rendering the common edges of the polygons. For example, triangles 25A and 25B have edge P.fwdarw.U in common. In many typical rendering techniques, the edge P.fwdarw.U may be rendered twice, firstly when rendering triangle 25A, and secondly when rendering triangle 25B. However, this is an inefficient process where the same pixel may be rendered more than one time thereby slowing the rendering process. In addition, other techniques may disregard rendering borders or use other non-consistent approaches such that there may be gaps on edge P.fwdarw.U that are not rendered during the rendering of either polygon. This results in gaps or blank spaces left in the middle of tessellated or overlapping polygons. Please note also that tesselated circle 25 may typically be a single color such as blue but that polygons 20 and 21 may be a different color such as red and green. In either of the above described cases, gaps which typically remain at the background color, which may be white, and may show through the polygon. In addition, if the edges are rendered multiple times, the edges between conflicting colors may be jagged and displeasing to the eye.
As a result of the above described problems, attempts have been made to provide a set of rules for filling polygons to prevent leaving gaps and also to prevent rendering the same pixels twice. One example of this has been promulgated by the M.I.T. (Massachusetts Institute of Technology) X-Consortium called the X-fill standard. The X-fill standard states that all pixels within the edges of a polygon are to be rendered or filled for that polygon. In addition, if a pixel is directly on or Just outside a polygon edge, then render the pixel only if the pixel is on the right side of the polygon being rendered.